import { Vector2 } from 'three';

/**
 *
 * @param {Vector2[]} points
 * @returns
 */
export function convexHull(points) {

    // 获取基准点
    var basePoint = getBasePoint(points);

    // 余弦值从大到小排序，基点会直接排在第一个
    points = quickSort(basePoint, points, 0, points.length - 1);

    // 获取离散点集凸多边形顶点
    return getPolygonVertexSet(points);
}

/**
 * 获取离散点集凸包
 * @param {Vector2[]} cosArr 排序后的离散点集
 * @returns {Vector2[]}
 */
function getPolygonVertexSet(cosArr) {

    // 结果数组
    var polygonArr = [];

    // 开始获取（按逆时针扫描，如果排序时升序则需要顺时针扫描）
    if (cosArr != null && cosArr.length > 0) {

        // 基点肯定是多边形顶点
        polygonArr.push(cosArr[0]);

        // 第一个夹角最小的点肯定是多边形顶点
        if (cosArr.length > 1) {
            polygonArr.push(cosArr[1]);
        }
        if (cosArr.length > 2) {
            polygonArr.push(cosArr[2]); //无论是否是多边形顶点直接放入（回溯中可能会被删除）
        }
        for (var i = 3; i < cosArr.length; i++) {
            var len = polygonArr.length;
            var leftVector = new Vector(
                polygonArr[len - 2],
                polygonArr[len - 1]
            );
            var rightVector = new Vector(polygonArr[len - 1], cosArr[i]);
            while (leftVector.cross(rightVector) < 0) {
                //向量叉积小于0时回溯
                polygonArr.splice(len - 1, 1); //删除最后一个元素
                len = polygonArr.length; //删除后，len有变化，需要重新设置
                leftVector = new Vector(polygonArr[len - 2], polygonArr[len - 1]);
                rightVector = new Vector(polygonArr[len - 1], cosArr[i]);
            }
            polygonArr.push(cosArr[i]);
        }
    }

    return polygonArr;
}


class Vector {

    /**
     *
     * @param {Vector2} start
     * @param {Vector2} end
     */
    constructor(start, end) {
        this.start = start;
        this.end = end;
        // 向量坐标
        this.x = this.end.x - this.start.x;
        this.y = this.end.y - this.start.y;

        this.cosx =
            this.x == 0 && this.y == 0
                ? 2
                : this.x / Math.sqrt(this.x * this.x + this.y * this.y);
    }
    /**
     *
     * @param {Vector} that
     * @returns
     */
    cross(that) {
        var result = this.x * that.y - that.x * this.y;

        return result;
    }
}

/**
 * 获取基点：在离散点集中选取y坐标最小的点，当作开始点
 * 如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点
 * @param vertexSet 离散点集
 * @returns {*}
 */
function getBasePoint(vertexSet) {
    if (vertexSet != null && vertexSet.length > 0) {
        var point = vertexSet[0];
        for (var i = 1; i < vertexSet.length; i++) {
            //最小y（多个y相同时，选择x最小的点）
            if (
                vertexSet[i].y < point.y ||
                (vertexSet[i].y == point.y && vertexSet[i].x < point.x)
            ) {
                point = vertexSet[i];
            }
        }

        return point;
    }

    return null;
}


function createRandomPoint() {

    var x = Math.random() * 100 - 50;
    var y = Math.random() * 100 - 50;

    return new Vector2(x, y);
}

/**
 * 随机生成n个不重合的离散点
 * @param n 离散点的个数
 * @returns {Array} 离散点集
 */
function getDiscretePointSet(n) {
    var vertexArray = [];
    if (n != null && n > 0) {
        for (var i = 0; i < n; i++) {
            var point = createRandomPoint(); //离散点
            //离散点不能有重合，重合点需要重新生成
            for (var j = 0; j < vertexArray.length; j++) {
                //注：此处理论上会出现死循环
                while (
                    point.x == vertexArray[j].x &&
                    point.y == vertexArray[j].y
                ) {
                    point = createRandomPoint();
                    j = 0; //重新生成点后从头开始新一轮比较
                }
            }
            vertexArray.push(point);
        }
    }

    return vertexArray;
}

/**
 * 对离散点排序：按照其与基点构成的向量与x轴正方向夹角余弦值快速降序
 * @param basePoint 基点
 * @param discretePointArray 需要排序的离散点集
 * @param left 左指示变量
 * @param right 右指示变量
 * @returns {*}
 */
function quickSort(basePoint, discretePointArray, left, right) {
    var i = left;
    var j = right;
    var temp = discretePointArray[left];
    var tempV = new Vector(basePoint, temp);
    while (i < j) {
        while (
            i < j &&
            tempV.cosx > new Vector(basePoint, discretePointArray[j]).cosx
        ) {
            j--;
        }
        if (i < j) {
            discretePointArray[i++] = discretePointArray[j];
        }
        while (
            i < j &&
            tempV.cosx < new Vector(basePoint, discretePointArray[i]).cosx
        ) {
            i++;
        }
        if (i < j) {
            discretePointArray[j--] = discretePointArray[i];
        }
    }
    discretePointArray[i] = temp;
    if (left < i) {
        quickSort(basePoint, discretePointArray, left, i - 1);
    }
    if (right > i) {
        quickSort(basePoint, discretePointArray, i + 1, right);
    }

    return discretePointArray;
}
